We address the problem of encrypted communication over insecure networks using computers whose contents can occasionally be studied by an adversary. Insecurity of the network means that it must be assumed that not necessarily every encrypted message reaches the intended receiver. The messages may be received at different order than they were sent. It is also expected that an adversary can now and then expose all of the cryptographical security data i.e. private keys and other data stored on participants' computers. The adversary then uses this exposed snapshot of security data (called shortly snapshot) to obtain as many previous or future plaintexts as possible. The presented method tries to make the damages of the security data exposure as small as possible.
Practical example is encrypted email communication. Even if every message would reach its destination the user may process only some of them and those in an ad hoc order. The user should be able to enjoy the backward security concept: An exposure of current security data should not compromise previously decrypted data. Clearly also the recovery i.e. the regaining of the state where the adversary cannot decrypt messages created after the snapshot would be a great advantage. It must be assumed that the user has no knowledge of the attackers success.
The usage of backward security was mentioned by Ross Anderson in an invited lecture in Fourth Annual Conference on Computer and Communications Security. ACM, 1997. Summary appears in: Two remarks on public key cryptology “http://www.cl.cam.ac.uk/users/rja14/”, 2001. Also the idea of protecting future communication after the exposure is discussed in the paper. According to Anderson in traditional (symmetric) systems, the backward security is provided by key updating: “two or more principals who share a key pass it through a one-way hash function at agreed times: Ki=h(Ki−1).” Because of the one-way function the previous key cannot be derived from the current key.
The future keys however can de derived by the attacker. To protect them “two or more principals who share a key hash it at agreed times with the messages they have exchanged since the last key change: Ki+1=h(Ki,Mi1,Mi2, . . . )”. Backward security is still provided and also protection of future messages if the attacker misses one previous message. As noted by Anderson the advent of public key cryptography and Diffie-Hellman (DH) key exchange offers a stronger form of protection: when fresh public DH keys have been exchanged the security has been regained even if all the previous traffic is decrypted by the opponent. In this invention the idea that some kind of representation of previous keys affects new ones is used together with the possibilities that the DH key exchange offers.
This recovery or freshness feature of the DH key exchange between two parties is widely used in the handshake phase of interactive session protocols. During the initial handshake the DH key exchange is performed and the shared secret is used as a security parameter for later message exchange. The individual messages during the session are then encrypted/decrypted on the basis of these parameters without any further DH exchange. If an attacker obtains the private key of one of the DH parties the whole session is exposed. This invention can also be seen as an approach to improve the security after the initial handshake. Please note that the communication need not necessarily be an online one. The presented protocol can naturally be used even if there are days between message movements—an example being email communication. Essential is that in the beginning the two communication parties are introduced to themselves via the protocol initialization.
The current literature that deals with the problem of backward security in digital signatures and in encryption uses public keys in their more traditional meaning: one public key is distributed to many persons, which can then use it to send encrypted messages to the creator of the public key. The backward security methods in current literature are developed for this more general case. In this invention however the public keys used are intended to be used only between two specific and fixed communication parties—the fixed sender and the fixed receiver. In this sense our keys could be called session keys between two parties. In our method when two persons send a message to the same receiver both senders use different public keys of the receiver. The senders have no knowledge of the public key the other sender uses. The more general case where only one public key is reserved for many senders leads to more complex solutions. Please note that the current literature also uses the term forward-security in the same sense we use the term backward security: a current exposure does not expose old decrypted communication. The first method for the general case is R. Canetti, S. Halevi, J. Katz: A Forward-Secure Public-Key Encryption Scheme. EUROCRYPT 2003, LNCS 2656, 255-271. Springer-Verlag, 2003. Their method does not provide recovery. The recovery is added by Y. Dodis, M. Franklin, J. Katz, A. Miyaji, M. Yung: Intrusion-Resilient Public-Key Encryption. Topics in Cryptology-CT-RSA 03, Lecture Notes in Computer Science Vol. 2612, M. Joye ed, Springer-Verlag, 2003. This approach uses special update and refresh messages.
If the presented protocol is used in e.g. email communication each new contact must be processed through the protocol initialization phase. If the methods based on the more general usage of public keys are used this need not be done—however a public key must have somehow been delivered to the sender of the first message. Our initialization requires that both parties send one initialization message. Our protocol provides backward security and recovers when messages are exchanged.
In symmetric encryption setting the problem of protecting old traffic is studied by M. Bellare, B. Yee: Forward-Security in Private-Key Cryptography. Extended abstract in Topics in Cryptology-CT-RSA 03, Lecture Notes in Computer Science Vol. 2612, M. Joye ed, Springer-Verlag, 2003. They recommend the usage of forward-secure pseudorandom bit generators to be used as a central primitive. This is our approach too. Their construction is such that the generator's input is a previous state (seed) and it generates a new state and the required random output bits. The old state is destroyed. If from the generated output bits it is infeasible to derive the previous state (seed) used, then the construction protects old outputs. To this construction we add another input: a Diffie-Hellman shared secret. This is added to provide the recovery feature. Our state is maintained in both computers and these states are required to go through same values during the communication.
By pseudorandomness it is understood to mean that it is infeasible to derive the initial seed from the outputted bits or another outputted bit from another ones and that if the seed is unknown the outputted bits are unpredictable. One construction that can be used is based upon the Goldreich-Levin hard-core bit and Blum-Micali iteration, see O. Goldreich, L. Levin: A Hard Core Predicate for any One Way Function. Proceedings, 21st ACM STOC, 1989, 25-32. and M. Blum, S. Micali: How to Generate Cryptographically Strong Sequences of Pseudo-random Bits. SIAM Journal of Computing, 13. no 4, 1986, 850-864. Another PRG providing similar properties i.e. pseudorandom bits can be used instead of this generator.
Let's now look the usage of DH exchange more closely. In traditional DH key exchange both parties send one message before the shared secret is computed and the actual encryption of the plaintext can be done. To provide optimal backward security and recovery one could do the DH exchange always before a plaintext should be encrypted. However, now only one third of the messages would carry information. Assume now that the attacker obtains one of the private keys. Then he could decrypt one cryptotext based on the obtained private key.
If the messaging would always happen in turns—every message is replied—the DH exchange could be done so that every message carries one new public key for immediate DH calculation to decrypt the encrypted text in the message and one another new public key for the next message to be received. Every private key would be destroyed after the DH calculation. Every message would carry information and again the attacker could only read one message based on one obtained private key.
Problems will arise if a participant is allowed to send many messages before receiving a new public key. The sender of many consecutive messages must use the most recently received public key for all the messages he sends. If the attacker obtains the corresponding private key the backward recovery will be lost, the attacker can read all messages decryptable by this private key even if he obtains the key just before the last such message is decrypted.
One development further would be to include a fixed number of new public keys in every message; the sender would prefer to use a public key only once. Suppose now that a sender will never use more messages than this fixed number before receiving a new set of public keys. Consider now the properties of such a system. There would be backward security and protocol would recover when the sender has received a new set of public keys. The presented invention will have backward security and recover at same time like this obvious fixed case but it uses only 3 new public keys in every message without a limit on the number of consecutive messages sent. One of the 3 keys is used for immediate DH calculation and two other ones are delivered to the message's receiver to be used in his next sendings.